一维差分

定义

差分涉及到两个数组，原数组和差分数组。原数组第 $i$ 位数是差分数组的前 $i$ 位的前缀和。

用途

用于 快速多次 给原数组某一个区间上的每一个数添加值或减去值。

实现

• 思路：在 $[l, r]$ 区间上加上数值 $a$，我们只需要在差分数组第 $l$ 位加上数值 $a$，在 $r+1$ 位减去数值 $a$，然后再求一次前缀和。
• 时间复杂度：
  1. 求差分数组：$O(n)$
  2. 给一个区间增加或减去一个值：$O(1)$
  3. 最后要求一次前缀和：$O(n)$

题目链接

Acwing链接

main

#include<iostream>
using namespace std;

const int N = 100010;
// a代表原数组，d代表差分数组，一开始全部为0
int a[N], d[N];
int n, m;

// 核心函数，利用这个函数给某个区间进行加减
void insert(int l, int r, int c);

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        // 这里直接利用insert来构造初始的差分数组d
        insert(i, i, a[i]);
    }
    while(m--)
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }
    
    // 将差分数组进行求前缀和
    for(int i = 1; i <= n; i++)
    {
        // a[0] = 0;
        a[i] = a[i - 1] + d[i];
        cout << a[i] << " ";
    }
    
    return 0;
}

利用差分数组对区间进行加减

void insert(int l, int r, int c)
{
    d[l] += c;
    d[r + 1] -= c;
}